A Sum-Product algorithm and a Min-Sum algorithm are known as fundamental algorithms used for decoding an LDPC coded signal. According to each of these decoding algorithms, a decoding apparatus decodes a received signal by calculating a log-likelihood ratio LLR (Log Likelihood Ratio) as probable reliability information on the received signal while performing an iterative operation on the received signal (for example, refer to nonpatent reference 1).
In the Sum-Product algorithm, arithmetic operations (e.g., an addition of real numbers and an evaluation of functions) using, for example, mathematical functions, such as a tan h function, are required, and therefore the calculation cost is high. For this reason, it is necessary to lower the calculation cost by, for example, preparing a table holding values of each of the functions in order to implement the Sum-Product algorithm. On the other hand, because exact arithmetic operations are performed in the Sum-Product algorithm, an advantage of improving the decoding performance is provided.
On the other hand, because simple equations which approximate the mathematical functions for use in the Sum-Product algorithm are used in the Min-Sum algorithm, the Min-Sum algorithm can be implemented via only four types of arithmetic operations including an addition, a judgment of a minimum, a judgment of whether a number is positive or negative, and a multiplication of the signs of positive and negative numbers. For this reason, the calculation cost becomes small. However, the decoding performance degrades under the influence of the approximation.
In the prior art decoding algorithms used for decoding an LDPC encoded signal, iterative decoding is carried out on the basis of transmission of probability information. In accordance with the Sum-Product algorithm and the Min-Sum algorithm, column processing is performed on all the bits of the encoded signal after all row processings on the encoded signal are completed at an arbitrary iteration of the iterative decoding.
For example, assuming that the check matrix of a LDPC code to be decoded is a binary m×n matrix H=[Hm,n] (n is an integer equal to or larger than 0 and smaller than N, and m is an integer equal to or larger than 0 and smaller than M), the row processing is performed on all members (m,n) which satisfy Hm,n=1 in order of m=1, 2, 3, . . . , and M, and, after that, the column processing is performed on all the members (m,n) which satisfy Hm,n=1 in order of n=1, 2, 3, . . . , and N.
For this reason, when the number of times that iteration is carried out in the decoding processing increases, there arises a problem that a delay which occurs in the decoding processing increases. To solve this problem, there has been provided a Shuffled BP (Belief Propagation) algorithm as a decoding algorithm which reduces the number of times of iterative decoding (for example, refer to nonpatent reference 2).
In accordance with the Shuffled BP algorithm, a calculation and an update of probability information with row processing and column processing are performed on an encoded signal in batches of 1 bit. Thus, the Shuffled BP algorithm provides an advantage of making it possible to carry out transmission of the probability information efficiently, thereby speeding up the convergence. Hereafter, this Shuffled BP algorithm will be explained briefly.
First, in an initialization step, the number of iterations i is set to i=1, a maximum number of iterations is expressed as Imax, and an initial value zm,n(0) of the log-likelihood ratio LLR (Log Likelihood Ratio) is defined as Fn(zm,n(0):=Fn). The check matrix H of the LDPC code to be decoded is a binary m×n matrix H=[Hm,n] (n is an integer equal to or larger than 0 and smaller than N, and m is an integer equal to or larger than 0 and smaller than M), and Hm,n is an element in the mth row and nth column of the matrix H.
Next, in step 1, a row process of computing the following equations (2) and (3) under a condition shown by the following equation (1) is carried out. Here, N(m) and M(n) are subsets of the set [1,N], and they are defined as follows: N(m):={n:Hm,n=1} and M(n):={m:Hm,n=1}. That is, N(m) means a set of column indices which have 1 in the mth row of the check matrix H, and M(n) means a set of column indices which have 1 in the mth row of the LDPC check matrix H.
                    [                  Equation          ⁢                                                            ⁢                                                          ⁢          1                ]                                                                      0          ≤          g          <                      G            ⁢                                                  ⁢                          (                                                g                  ⁢                                      :                                    ⁢                                                                          ⁢                  Integer                                ,                                  G                  =                                      N                    /                                          N                      g                                                                                  )                                      ⁢                                  ⁢                                                            g                ·                                  N                  g                                            +              1                        ≤            n            ≤                                          (                                  g                  +                  1                                )                            ·                              N                g                                              ,                      m            ∈                          M              ⁡                              (                n                )                                                                        (        1        )                                          τ                      m            ,            n                                (            i            )                          =                              ∏                                                            n                  ′                                ∈                                                      N                    ⁡                                          (                      m                      )                                                        ∖                  n                                                                              n                  ′                                ≤                                  g                  ·                                      N                    g                                                                                ⁢                                          ⁢                                    tanh              ⁡                              (                                                      z                                          m                      ,                                              n                        ′                                                                                    (                      i                      )                                                        /                  2                                )                                      ⁢                                          ∏                                                                            n                      ′                                        ∈                                                                  N                        ⁡                                                  (                          m                          )                                                                    ∖                      n                                                                                                  n                      ′                                        ≥                                                                  g                        ·                                                  N                          g                                                                    +                      1                                                                                  ⁢                                                          ⁢                              tanh                ⁡                                  (                                                            z                                              m                        ,                                                  n                          ′                                                                                            (                                                  i                          -                          1                                                )                                                              /                    2                                    )                                                                                        (        2        )                                          ɛ                      m            ,            n                                (            i            )                          =                  log          ⁢                                    1              +                              τ                                  m                  ,                  n                                                  (                  i                  )                                                                    1              -                              τ                                  m                  ,                  n                                                  (                  i                  )                                                                                        (        3        )            
In addition, a set which is acquired by removing an element a from a set A is expressed as A\a. In other words, N(m)\n shows a set of column indices in which the nth column is removed from the set N(m), and M(n)\m shows a set of row indices in which the mth row is removed from the set M(n). zm,n′(i) is an LLR which is updated at the ith iteration, and εm,n(i) is an LLR at the ith iteration which is sent from a check node to a bit node.
Furthermore, in step 1, a column process of computing the following equations (4) and (5) under the condition shown by the above-mentioned equation (1) is carried out. Here, zm,n(i) is an LLR at the ith iteration which is sent from the bit node to the check node. Furthermore, zn(i) is a posterior value at the ith iteration.
                    [                  Equation          ⁢                                                            ⁢                                                          ⁢          2                ]                                                                      z                      m            ,            n                                (            i            )                          =                              F            n                    +                                    ∑                                                m                  ′                                ∈                                                      M                    ⁡                                          (                      n                      )                                                        ∖                  m                                                      ⁢                                                  ⁢                          ɛ                                                m                  ′                                ,                n                                            (                i                )                                                                        (        4        )                                          z          η                      (            i            )                          =                              F            n                    +                                    ∑                              m                ∈                                  M                  ⁡                                      (                    n                    )                                                                        ⁢                                                  ⁢                          ɛ                              m                ,                n                                            (                i                )                                                                        (        5        )            
Next, in step 2, a hard decision of the posterior value zn(i) is carried out, and a decoded sequence shown by the following equation (6) is created. Then, if a condition shown by the following equation (7) is satisfied, the sequence shifts to a process of step 3 which will be mentioned later, and, if neither of the these two conditions is satisfied, the number of iterations i is incremented, and the sequence returns to the process of step 2. In step 3, the decoded sequence according to the following equation (6), which is acquired in step 2, is outputted as a decoded result. wn in the following equation (6) is an element at n=1 to N of the decoded sequence w.[Equation 3]w=[wn]  (6)[Equation 4]Parity check: OK(H·w=0)orMaximum number of iterations i=Imax  (7)
In the above-mentioned Shuffled BP algorithm, focusing attention to the number of iterations i, it is understood that transmission of the probability information is carried out efficiently by carrying out the row processing using zm,n′(i) which is an LLR updated at the same ith iteration.
In accordance with nonpatent reference 2, a case in which a calculation and an update of the probability information with row processing and column processing are performed on the received signal in batches of 1 bit, assuming Ng=1, is defined as the Shuffled BP algorithm, and a case in which a calculation and an update of the probability information with row processing and column processing are performed on the received signal in batches of two or more predetermined bits, assuming 1<Ng<N, is defined as the Group Shuffled BP algorithm. This specification follows these definitions. The case of Ng=N is defined as the Sum-Product algorithm. For the sake of simplicity, Ng is a divisor of N.
On the other hand, as decoding algorithms of decoding an LDPC code at much the same calculation cost as the Min-Sum algorithm, and of being able to reduce the degradation in the decoding performance, as compared with the Sum-Product algorithm, the Normalized BP algorithm and the Offset BP algorithm have been proposed (for example, refer to nonpatent reference 3).
To be brief, in accordance with the Normalized BP algorithm, because an LLR which is calculated with the Min-Sum algorithm is always larger than an LLR which is calculated with the Sum-Product algorithm, an LLR which is calculated through row processing according to the Min-Sum algorithm is divided by a factor α (>1) which is called a normalization factor, and is then delivered. Furthermore, in accordance with the Offset BP algorithm, an LLR calculated through row processing based on the Min-Sum algorithm is subtracted from a factor β (>0) which is called an offset factor, and is then delivered.
Thus, although division and subtraction operations are performed when decoding an LDPC code, increase in the calculation cost due to the division and subtraction operations is not so big, and therefore the degradation in the decoding performance can be reduced as compared with the case of using the Sum-Product algorithm. Each of the factors α and β only has to be calculated beforehand using a simulation or a density evolution method (for example, refer to nonpatent reference 4), and held by an LDPC decoding unit.
Furthermore, there has been provided an algorithm of correcting for an LLR calculated through the row processing based on the Min-Sum algorithm according to the magnitude of the received signal (for example, refer to nonpatent reference 5). In accordance with this decoding algorithm, a table of a correction function is prepared as a correction term of the Min-Sum algorithm, and a precise correction is made by changing the correction term according to the magnitude of the received signal so that the decoding performance is improved.
In addition, there has been provided a method of controlling the sequence of operations of the Shuffled BP algorithm according to the magnitude of a received LLR as communication path information. In accordance with this method, received LLRs calculated from received information are ranked in order of decreasing absolute value or increasing absolute value, and are decoded according to the Shuffled BP algorithm.
As fundamental algorithms of decoding a turbo encoded signal, the Log-MAP (Maximum A Posteriori Probability) algorithm and the Max-Log-Map algorithm have been proposed. According to these decoding algorithm, while a metric value is calculated as probable reliability information on the received signal, an iterative operation is performed on the received signal so that it is decoded (for example, refer to nonpatent reference 6).
According to the Log-MAP algorithm, arithmetic operations (e.g., an addition of a real number and an evaluation of a function) using, for example, a mathematical function, such as an exponential function, are required, and therefore the calculation cost is high. For this reason, it is necessary to lower the calculation cost by, for example, preparing a table holding values of the function in order to implement the Log-MAP algorithm. In contrast, because precise operations are performed according to the Log-MAP algorithm, an advantage of improving the decoding performance is provided.
On the other hand, because a simple equation which approximates the mathematical function of the Log-Map algorithm is used in the Max-Log-MAP algorithm, the Max-Log-MAP algorithm can be implemented via only four types of arithmetic operations including an addition, a judgment of a maximum, a judgment of whether a number is positive or negative, and a multiplication of the signs of positive and negative numbers. A logarithm computation for the sum of an exponential function which is carried out in the Log-MAP algorithm is approximated by a maximum of an exponent. For this reason, because the process containing the mathematical function can be eliminated, the calculation cost can be reduced. However, the decoding performance degrades under the influence of the approximation.
On the other hand, there has been provided a decoding algorithm of decoding a turbo code at much the same calculation cost as the Max-Log-MAP algorithm, and of being able to reduce the degradation in the decoding performance, as compared with the Map algorithm (for example, refer to nonpatent reference 7).
To be brief, a metric value calculated through a metric calculation based on the Max-Log-Map algorithm is defined as an LLR which is adjusted to a value which is much the same as that which is multiplied by a factor s and is calculated according to the MAP algorithm, and which is delivered.
Thus, although multiplications are performed when a turbo code is decoded, the increase in the calculation cost due to the multiplications is not so big, and the degradation in the decoding performance can be reduced as compared with the case of using the Log-MAP algorithm. Furthermore, the factor s only has to be calculated in advance using a simulation, and held by a turbo decoding unit.    [Nonpatent reference 1] Tadashi Wadayama, “Low-Density Parity-Check Code, and Decoding method LDPC (Low Density Parity Check) code/Sum-Product Decoding Method”, Triceps, Jun. 5, 2002, pp. 76-99    [Nonpatent reference 2] Juntan Zhang et al., “Shuffled Belief Propagation Decoding”, [online], [retrieved on Sep. 28, 2004], http://lester.univ-ubs.fr:8080/˜boutillon/Journee_GDR_LDPC/Fossorier1_GDR_LDPC.pdf    [Nonpatent reference 3] Jinghu Chen et al., “Reduced-Complexity Decoding of LDPC Codes”, [online], [retrieved on Sep. 28, 2004], http://www-ee.eng.hawaii.edu/˜jinghu/FILES/tcom02v3p2.pdf    [Nonpatent reference 4] Jinghu Chen et al., “Density evolution of two improved BP-based algorithms for LDPC decoding”, IEEE Communications Letters, March 2002    [Nonpatent reference 5] Xiao-Yu et al., “Efficient Implementation of the Sum-Product algorithm for Decoding LDPC Codes”, Proc. 2001 IEEE GlobeCom Conf., pp. 1036-1036E, November 2001    [Nonpatent reference 6] Haruo Hagiwara, “Foundation of turbo Code”, Triceps, Oct. 7, 1999, pp. 37-46    [Nonpatent reference 7] J Vogt et al., “Improving the max-log-MAP turbo decoder”, ELECTRONICS LETTERS, Vol. 36, No. 23, p. 1937-1938
A problem with prior art decoding apparatus for decoding an LDPC encoded signal according to the Min-Sum algorithm is that the number of iterations must increase in order to maintain the decoding performance, and therefore a decoding delay also becomes large with this increase in the number of iterations. This tendency also appears in both the Normalized BP algorithm which uses an approximation update equation based on the Min-Sum algorithm as a fundamental update equation, and the Offset BP algorithm.
The decoding performance of the Normalized BP algorithm and that of the Offset BP algorithm are greatly dependent upon the values of the factor α (normalization factor) and factor β (offset factor), respectively. For this reason, in the case of each of the Normalized BP algorithm and Offset BP algorithm, although it is necessary to calculate each of the factors α and β in advance, sufficient decoding performance cannot be achieved if the value of each of the factors α and β is not changed dependently upon the construction of codes and the communication path when actually implemented in a receiving apparatus or the like.
Furthermore, with the decoding algorithm of correcting for an LLR calculated through the row processing based on the Min-Sum algorithm according to the magnitude of the received signal, it is necessary to provide a correction term table for holding a correction constant according to the received information (i.e., the magnitude of the received signal), and therefore it is not easy to implement the decoding algorithm. Also in a case of an algorithm which needs a mathematical function, such as a tan h function, when decoding a code, such as the Sum-Product algorithm or the Shuffled BP algorithm, the calculation cost becomes high and the hardware structure becomes complicated and therefore it is difficult to implement the algorithm.
Furthermore, with the Shuffled BP algorithm and the Group Shuffled BP algorithm, a decoding operation is sequentially performed on a code in batches of one bit from the leading bit of the code, or a decoding operation is sequentially performed on the code in batches of two or more bits from the leading two or more bits of the code. A problem with the Shuffled BP algorithm and the Group Shuffled BP algorithm is therefore that it is impossible to provide an optimal sequence of operations for the code construction and the modulation method. Another problem with the technology for controlling the sequence of operations according to the magnitudes of received LLRs, as communication path information, calculated from the received information is that it is necessary to change the sequence of operations every time when LLRs are received.
Furthermore, the decoding performance of the Max-Log-MAP algorithm for multiplying the value by the above-mentioned factor s depends upon the value of the factor s. For this reason, although it is necessary to calculate the factor s in advance, sufficient decoding performance cannot be achieved if the value of the factor s is not changed dependently upon the construction of codes and the communication path when actually implemented in a receiving apparatus or the like.
The present invention is made in order to solve the above-mentioned problems, and it is therefore an object of the present invention to provide a decoding method of and a decoding apparatus for decoding an encoded signal by providing an efficient probability transmission algorithm for the Min-Sum algorithm, and the Normalized BP algorithm and the Group Shuffled BP algorithm which use a fundamental update equation based on the Min-Sum algorithm, thereby speeding up the convergence of operation results and reducing the number of times that iterative decoding is carried out, and a communications apparatus provided with the decoding apparatus.
It is another object of the present invention to provide a decoding apparatus which can have a high decoding capability at a calculation cost which is much the same as that of the Min-Sum algorithm without using a complicated mathematical function, unlike the Sum-Product algorithm, without being greatly dependent on factors, unlike the Normalized BP algorithm and the Offset BP algorithm, and without having to hold a correction term as a table, and a communications apparatus provided with the decoding apparatus.
It is a further object of the present invention to provide a decoding apparatus which even when a received code has been multi-level modulated and transmitted thereto, and even when the received code is an irregular LDPC code, can efficiently carry out control of the sequence of operations of a decoding algorithm of performing a calculation and an update of probability information with row processing and column processing on the received signal in batches of one 1 bit or two or more predetermined bits, and can also reduce the number of iterations, and a communications apparatus provided with the decoding apparatus.
It is a still further object of the present invention to provide a decoding apparatus which when a received code has been multi-level modulated and transmitted thereto, improves the decoding performance thereof by determining a factor α (normalization factor) or a factor β (offset factor) dependently upon the modulation method and the code construction, and a communications apparatus provided with the decoding apparatus.
It is another object of the present invention to provide a decoding apparatus which can reduce an operation delay time by parallelizing a process of performing a calculation and an update of probability information with row processing and column processing on the received signal in batches of one 1 bit or two or more predetermined bits, like the Shuffled BP algorithm, and a communications apparatus provided with the decoding apparatus.
It is a further object of the present invention to provide a decoding apparatus which can have a high decoding capability at a calculation cost which is much the same as that of the Max-Log-MAP algorithm without using a complicated mathematical function, unlike the Log-MAP algorithm, and a communications apparatus provided with the decoding apparatus.